class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash1;   // 保存words里面所有单词的频次
        for(auto& s : words) hash1[s]++;

        int len = words[0].size(), m = words.size();
        vector<int> ret;
        for(int i = 0; i < len; i++)    // 执行len次
        {
            unordered_map<string, int> hash2;   // 维护窗口内单词的频次
            for(int left = i, right = i, cnt = 0; right + len <= s.size(); right += len)
            {
                // 进窗口 + 维护cnt
                string in = s.substr(right, len);
                hash2[in]++;
                if(hash2[in] <= hash1[in]) cnt++;

                // 判断
                if(right - left + 1 > len * m)
                {
                    // 出窗口 + 维护cnt
                    string out = s.substr(left, len);
                    if(hash2[out] <= hash1[out]) cnt--;
                    hash2[out]--;
                    left += len;
                }

                // 更新结果
                if(cnt == m)
                    ret.push_back(left);
            }
        }

        return ret;
    }
};

//=================================================================================
// 优化
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash1;   // 保存words里面所有单词的频次
        for(auto& s : words) hash1[s]++;

        int len = words[0].size(), m = words.size();
        vector<int> ret;
        for(int i = 0; i < len; i++)    // 执行len次
        {
            unordered_map<string, int> hash2;   // 维护窗口内单词的频次
            for(int left = i, right = i, cnt = 0; right + len <= s.size(); right += len)
            {
                // 进窗口 + 维护cnt
                string in = s.substr(right, len);
                hash2[in]++;
                if(hash1.count(in) && hash2[in] <= hash1[in]) cnt++;

                // 判断
                if(right - left + 1 > len * m)
                {
                    // 出窗口 + 维护cnt
                    string out = s.substr(left, len);
                    if(hash1.count(out) && hash2[out] <= hash1[out]) cnt--;
                    hash2[out]--;
                    left += len;
                }

                // 更新结果
                if(cnt == m)
                    ret.push_back(left);
            }
        }

        return ret;
    }
};
